// https://www.lintcode.cn/problem/decode-ways/
// TLE
// class Solution {
// public:
//     /**
//      * @param s: a string,  encoded message
//      * @return: an integer, the number of ways decoding
//      */
     
//     void getDecodings(string &s, vector<string>& vec, string tmp, int pos)
//     {
//         // if (tmp.length() == s.length())
//         if (pos >= s.length())
//         {
//             vec.push_back(tmp);
//             return;
//         }
//         // for (int i = pos; i < s.length(); ++i)
//         // { 
//             // if (s[i] > '0') getDecodings(s, vec, tmp + char('A' + (s[i] - '0')), pos + 1); //注意显式转换成char，不然就是int
//             // if (i < s.length() - 1 && (s[i] == '1' || (s[i] == '2' && s[i + 1] <= '6')))
//             // {
//             //     getDecodings(s, vec, tmp + char('A' + ((s[i] - '0') * 10 + s[i + 1] - '0')), pos + 2);
//             //     i++; // 别忘了
//             // }
//         // }
//         if (s[pos] > '0') getDecodings(s, vec, tmp + char('A' + (s[pos] - '0')), pos + 1); //注意显式转换成char，不然就是int
//         if (pos < s.length() - 1 && (s[pos] == '1' || (s[pos] == '2' && s[pos + 1] <= '6')))
//         {
//             getDecodings(s, vec, tmp + char('A' + ((s[pos] - '0') * 10 + s[pos + 1] - '0')), pos + 2);
//         }
//     }
//     int numDecodings(string &s) {
//         if (s.empty()) return 0;
//         vector<string> vec;
//         getDecodings(s, vec, "", 0);
//         int result = vec.size();
//         return result;
//     }
// };

// 动态规划 考虑f(i + 1) 和f(i) f(i + 1)的关系
class Solution {
public:
    /**
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    int numDecodings(string &s) {
        if (s.empty()) return 0;
        int l = s.length();
        vector<int> record(l + 1, 0);
        record[0] = 1;
        for (int i = 0; i < s.length(); ++i)
        {
            if (s[i] != '0') record[i + 1] = record[i];
            if (i >= 1 && (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6'))) record[i + 1] += record[i - 1];
        }
        return record[l];
    }
};